import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Test {
    // 题目1 ：移动所有球到每个盒子所需的最小操作数
    // 有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。
    //
    //在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。
    //
    //返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。
    //
    //每个 answer[i] 都需要根据盒子的 初始状态 进行计算。
    public int[] minOperations(String boxes) {
        char[] ball = boxes.toCharArray();
        int n = ball.length;
        int left = ball[0] - '0';
        int right = 0;
        int[] dp = new int[n];
        for(int i = 1; i < n; i++){
            if(ball[i] == '1'){
                right++;
                dp[0] += i;
            }
        }

        for(int i = 1; i < n; i++){
            dp[i] = dp[i - 1] + left - right;
            if(ball[i] == '1'){
                left++;
                right--;
            }
        }
        return dp;
    }

    // 题目 2： N 字形变换
    // 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
    //
    //比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
    //
    //P   A   H   N
    //A P L S I I G
    //Y   I   R
    //之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
    //
    //请你实现这个将字符串进行指定行数变换的函数：
    //
    //string convert(string s, int numRows);
    public String convert(String s, int numRows) {
        if(numRows < 2){
            return s;
        }
        List<StringBuilder> rows = new ArrayList<>();
        for(int i = 0; i < numRows; i++){
            rows.add(new StringBuilder());
        }
        int i = 0;
        int flag = -1;
        for(char x : s.toCharArray()){
            rows.get(i).append(x);
            if(i == 0 || i == numRows - 1){
                flag = -flag;
            }
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows){
            res.append(row);
        }
        return res.toString();
    }

    // 题目 3：罗马数字转整数
    // 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
    //
    //字符          数值
    //I             1
    //V             5
    //X             10
    //L             50
    //C             100
    //D             500
    //M             1000
    //例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
    //
    //通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
    //
    //I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
    //X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
    //C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
    //给定一个罗马数字，将其转换成整数。

    // 自己的思路是，按照 1 位 或 两位进行读取，做一个累加，实现起来较为繁琐。
    // 题解：大数小数，大数为正数，小数大数，小数为负数
    public int romanToInt(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        int sum = 0;
        for(int i = 0; i < n - 1; i++){
            int left = romeToNum(c[i]);
            int right = romeToNum(c[i + 1]);
            if(left < right){
                sum -= left;
            }else{
                sum += left;
            }
        }
        return sum += romeToNum(c[n - 1]);
    }

    private int romeToNum(char c){
        int ans = 0;
        switch(c){
            case 'I':
                ans = 1;
                break;
            case 'V':
                ans = 5;
                break;
            case 'X':
                ans = 10;
                break;
            case 'L':
                ans = 50;
                break;
            case 'C':
                ans = 100;
                break;
            case 'D':
                ans = 500;
                break;
            case 'M':
                ans = 1000;
                break;
        }
        return ans;
    }

    // 题目 4 ：整数转化成罗马数字

    public String intToRoman1(int num) {
        StringBuilder stringBuilder = new StringBuilder();
        while(num >= 1){
            if(num >= 1000){
                stringBuilder.append("M");
                num -= 1000;
            }else if( num >= 900){
                stringBuilder.append("CM");
                num -= 900;
            }
            else if(num >= 500 ){
                stringBuilder.append("D");
                num -= 500;
            }else if(num >= 400){
                stringBuilder.append("CD");
                num -= 400;
            }else if(num >= 100 ){
                stringBuilder.append("C");
                num -= 100;
            }else if(num >= 90 ){
                stringBuilder.append("XC");
                num -= 90;
            }else if(num >= 50 ){
                stringBuilder.append("L");
                num -= 50;
            }
            else if(num >= 40){
                stringBuilder.append("XL");
                num -= 40;
            }else if(num >= 10 ){
                stringBuilder.append("X");
                num -= 10;
            }else if(num >= 9){
                stringBuilder.append("IX");
                num -= 9;
            }
            else if(num >= 5){
                stringBuilder.append("V");
                num -= 5;
            }else if(num >= 4){
                stringBuilder.append("IV");
                num -= 4;
            }else if(num >= 1){
                stringBuilder.append("I");
                num -= 1;
            }
        }
        return stringBuilder.toString();
    }

    // 下面的方法是上面的简化，思想一样。
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] rome = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

    public String intToRoman(int num) {
        StringBuilder stringBuilder = new StringBuilder();

        for(int i = 0; i < values.length; i++){
            int value = values[i];
            String symbol = rome[i];
            while(num >= value){
                num -= value;
                stringBuilder.append(symbol);
            }
            if(num == 0){
                break;
            }
        }
        return stringBuilder.toString();
    }

    // 题目 5：统计匹配检索规则的物品数量
    // 给你一个数组 items ，其中 items[i] = [typei, colori, namei] ，描述第 i 件物品的类型、颜色以及名称。
    //
    //另给你一条由两个字符串 ruleKey 和 ruleValue 表示的检索规则。
    //
    //如果第 i 件物品能满足下述条件之一，则认为该物品与给定的检索规则 匹配 ：
    //
    //ruleKey == "type" 且 ruleValue == typei 。
    //ruleKey == "color" 且 ruleValue == colori 。
    //ruleKey == "name" 且 ruleValue == namei 。
    //统计并返回 匹配检索规则的物品数量 。
    public int countMatches1(List<List<String>> items, String ruleKey, String ruleValue) {
        int count = 0;
        for(List<String> item : items){
            if(ruleKey.equals("type")){
                if(item.get(0).equals(ruleValue) ){
                    count++;
                }
            }else if(ruleKey.equals("color")){
                if(item.get(1).equals(ruleValue)){
                    count++;
                }
            }else{
                if(item.get(2).equals(ruleValue)){
                    count++;
                }
            }
        }
        return count;
    }

    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("type", 0);
        map.put("color", 1);
        map.put("name", 2);

        int index = map.get(ruleKey);

        int res = 0;

        for(List<String> item : items){
            if(item.get(index).equals(ruleValue)){
                res++;
            }
        }
        return res;
    }

    // 题目 6：十-二进制数的最少数目
    // 如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。
    //
    //给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。
    // 问题转换成了 n 中最大的数字！
    public int minPartitions(String n) {
        char[] ch = n.toCharArray();
        int len = ch.length;
        int max = 0;
        for(int i = 0; i < len; i++){
            int num = ch[i] - '0';
            if(num == 9){
                return 9;
            }
            max = Math.max(max, num);
        }
        return max;
    }


    // 题目7：
    // 请你设计一个可以解释字符串 command 的 Goal 解析器 。
    // command 由 "G"、"()" 和 "(al)" 按某种顺序组成。
    // Goal 解析器会将 "G" 解释为字符串 "G"
    // "()" 解释为字符串 "o" ，"(al)" 解释为字符串 "al"
    // 然后，按原顺序将经解释得到的字符串连接成一个字符串。
    //给你字符串 command ，返回 Goal 解析器 对 command 的解释结果。

    // 这个题注意字符串中 replace 、 replaceAll 、replaceFirst 方法的区别
    public static String interpret1(String command) {
        return command.replace("()", "o").replace("(al)", "al");
    }

    public static void main1(String[] args) {
        String ret = interpret("G()(al)");
        System.out.println(ret);
    }

    public static String interpret(String command) {
        char[] ch = command.toCharArray();
        int n = ch.length;
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < n; i++){
            if(ch[i] == 'G'){
                res.append("G");
            }
            if(ch[i] == '('){
                if(ch[i + 1] == ')'){
                    res.append("o");
                }else{
                    res.append("al");
                }
            }
        }
        return res.toString();
    }

    // 题目8 ：动态口令
    // 某公司门禁密码使用动态口令技术。初始密码为字符串 password，密码更新均遵循以下步骤：
    //
    //设定一个正整数目标值 target
    //将 password 前 target 个字符按原顺序移动至字符串末尾
    //请返回更新后的密码字符串。

    public String dynamicPassword1(String password, int target) {
        String str1 = password.substring(0, target);
        String str2 = password.substring(target, password.length());
        return str2 + str1;
    }

    // 将两个相同的字符串拼在一起，取子串！
    // 十分巧妙！
    public String dynamicPassword(String p, int len) {
        return (p + p).substring(len, p.length() + len);
    }


    public static void main2(String[] args) {
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> fir = new ArrayList<>();
        fir.add(1);
        lists.add(fir);
        System.out.println(lists.toString());
    }

    // 题目9 ：杨辉三角形
    // 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
    public List<List<Integer>> generate1(int numRows) {
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> fir = new ArrayList<>();
        fir.add(1);
        lists.add(fir);
        if(numRows == 1){
            return lists;
        }
        for(int i = 1; i < numRows; i++){
            List<Integer> list = new ArrayList<>();
            list.add(1);
            for(int j = 1; j < i; j++){
                List<Integer> temp = lists.get(i - 1);
                list.add(temp.get(j) + temp.get(j - 1));
            }
            list.add(1);
            lists.add(list);
        }
        return lists;
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> lists = new ArrayList<>();
        for(int i = 0; i < numRows; i++){
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    list.add(1);
                }else{
                    List<Integer> temp = lists.get(i - 1);
                    list.add(temp.get(j) + temp.get(j - 1));
                }
            }
            lists.add(list);
        }
        return lists;
    }

    // 题目10 ：杨辉三角形 Ⅱ
    // 使用两个列表来回倒腾！！
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i <= rowIndex; i++){
            List<Integer> temp = new ArrayList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    temp.add(1);
                }else{
                    temp.add(list.get(j) + list.get(j - 1));
                }
            }
            list = temp;
        }
        return list;
    }

    // 题目11 ： 相同的树
    // 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    //
    //如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。


    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }

        if(p == null || q == null){
            return false;
        }

        if(p.val != q.val){
            return false;
        }

        boolean left =  isSameTree(p.left, q.left);
        if(!left){
            return false;
        }
        boolean right = isSameTree(p.right, q.right);
        if(!right){
            return false;
        }
        return true;
    }

    // 题目 12：对称二叉树
   // 给你一个二叉树的根节点 root ， 检查它是否轴对称。
    // 是否对称，意味着根节点的左子树与右子树是否镜像相等。
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }

        return dsf1(root.left, root.right);
    }

    private boolean dsf1(TreeNode l, TreeNode r){
        if(l == null && r == null){
            return true;
        }

        if(l == null || r == null){
            return false;
        }

        if(l.val != r.val){
            return false;
        }

        return dsf1(l.left, r.right) && dsf1(l.right, r.left);
    }

    // 题目 13：二叉树的最大深度
    // 给定一个二叉树 root ，返回其最大深度。
    //二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
    public static int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    public static void main3(String[] args) {
        TreeNode tree = new TreeNode(1);
        TreeNode tree1 = new TreeNode(3);
        tree.right = tree1;
        int res = maxDepth(tree);
        System.out.println(res);
    }

    // 题目 14 ：翻转二叉树
   // 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    // 我的思路是从上到下
    public TreeNode invertTree1(TreeNode root) {
        if(root == null){
            return root;
        }

        dsf(root, root.left, root.right);

        return root;
    }

    private void dsf(TreeNode root, TreeNode l, TreeNode r){
        if(l == null && r == null ){
            return;
        }

        root.left = r;
        root.right = l;

        if(l != null){
            dsf(l, l.left, l.right);
        }

        if(r != null){
            dsf(r, r.left, r.right);
        }
    }

    // 题解的思路是从下往上
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }

        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        root.left = right;
        root.right = left;

        return root;
    }
































}
